package com.acwing.partition13;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/2/15 12:01
 */
public class AC1277维护序列 {

    private static final int N = 100010;
    private static Node[] tr = new Node[N << 2];
    private static int[] nums = new int[N];

    private static int n = 0, m = 0, p = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        p = Integer.parseInt(ss[1]);
        ss = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++) nums[i] = Integer.parseInt(ss[i - 1]);
        build(1, 1, n);
        m = Integer.parseInt(reader.readLine());
        while (m-- > 0) {
            ss = reader.readLine().split(" ");
            int op = Integer.parseInt(ss[0]), l = Integer.parseInt(ss[1]), r = Integer.parseInt(ss[2]);
            if (op == 1) {
                int d = Integer.parseInt(ss[3]);
                modify(1, l, r, 0, d);
            } else if (op == 2) {
                int d = Integer.parseInt(ss[3]);
                modify(1, l, r, d, 1);
            } else {
                writer.write(query(1, l, r) + "\n");
            }
        }
        writer.flush();
    }

    private static void eval(Node root, long add, long mul) {
        root.sum = (root.sum * mul + (root.r - root.l + 1) * add % p) % p;
        root.mul = root.mul * mul % p;
        root.add = (root.add * mul + add) % p;
    }

    private static void pushdown(int u) {
        eval(tr[u << 1], tr[u].add, tr[u].mul);
        eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
        //最后清空一下标记
        tr[u].add = 0;
        tr[u].mul = 1;
    }

    private static long query(int u, int l, int r) {
        if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
        pushdown(u);
        long res = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) res = query(u << 1, l, r);
        if (r > mid) res = (res + query(u << 1 | 1, l, r)) % p;
        return res;
    }

    private static void modify(int u, int l, int r, int add, int mul) {
        if (l <= tr[u].l && r >= tr[u].r) eval(tr[u], add, mul);
        else {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if (l <= mid) modify(u << 1, l, r, add, mul);
            if (r > mid) modify(u << 1 | 1, l, r, add, mul);
            pushup(u);
        }
    }

    private static void pushup(int u) {
        tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
    }

    private static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Node(l, r, nums[l], 0, 1);
        else {
            tr[u] = new Node(l, r, 0, 0, 1);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    private static class Node {
        private int l, r;
        private long sum, add, mul;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }

        public Node(int l, int r, long sum, long add, long mul) {
            this.l = l;
            this.r = r;
            this.sum = sum;
            this.add = add;
            this.mul = mul;
        }
    }
}
